МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ Структура даних БІНАРНЕ ДЕРЕВО ПОШУКУ МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи № 6 для студентів напряму 6.050102 “Комп’ютерна інженерія” Львів – 2010 Методичні вказівки до лабораторної роботи "Структура даних БІНАРНЕ ДЕРЕВО ПОШУ-КУ" для підготовки студентів напрямку 6.0915 “Комп’ютерна інженерія” / Укл. Т.А.Лисак – Львів: Видавництво НУ “Львівська політехніка”, 2010 – 16 с. Укладач: Лисак Т.А., ст. викладач каф.ЕОМ Відповідальний за випуск: Мельник А.О., д-р техн. наук, проф. Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ Юрчак І.Ю., доцент кафедри САПР, к.т.н.  1. МЕТА РОБОТИ Вивчення абстрактної структури даних "Бінарне дерево пошуку". Набуття практичних навичок побудови дерева та використання його для розв'язання прикладних задач. 2. ТЕОРЕТИЧНІ ВІДОМОСТІ Дерево - в інформатиці та програмуванні одна з найпоширеніших структур даних. Формально дерево визначається як скінченна множина Т з одного або більше вузлів (nodes), яка задовольняє наступним вимогам: існує один відокремлений вузол - корень (root) дерева інші вузли (за виключенням кореня) розподілені серед m ≥ 0 непересічних множин T1, ..., Tm і кожна з цих множин в свою чергу є деревом. Дерева T1, ..., Tm мають назву піддерев (subtrees) даного кореня.
З цього визначення випливає, що кожний вузлів є в свою чергу коренем деякого піддерева. Кількість піддерев вузла має назву степеня (degree) цього вузла. Вузол степеню нуль називається кінцевим (terminal) або листком (leaf). Не корінь і некінцевий вузол також має назву вершини розгалуження (branch node). Нехай x - довільний вузол дерева з коренем r. Тоді існує єдиний шлях з r до x. Усі вузли на цьому шляху називаються предками (ancestors) x; якщо деякий вузол y є предком x, то x називається нащадком (descendant) y. 3. ПОРЯДОК ВИКОНАННЯ РОБОТИ 1. При підготовці до лабораторної роботи, необхідно засвоїти теоретичний матеріал по темі і підготуватись до контрольного опитування по розумінню питань даної тематики. 2. Згідно з індивідуальним завданням розробити алгоритм розв’язання задачі. 3. Підготувати програмну реалізацію розробленого алгоритму. Засобами вбудованого текстового редактора інтегрованого середовища набрати текст підготовленої програми. Відкомпілювати, налагодити та виконати програму. 4. Протестувати програму згідно зі складеною системою тестів і, при потребі, підкоректувати текст програми. Проаналізувати отримані результати. 5. Написати контрольне опитування по темі. 6. Оформити звіт по роботі. Без підготовкі до роботи (програмної реалізації розробленого алгоритму) студент до роботи не допускається. 4. ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ 4.1. Вибір варіанта індивідуального завдання № варіанта = [(місяць народження) + (ASCII–код другої літери прізвища – мала латинська літера)] % 20 + 1 4.2. Варіанти завдань Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати: послідовність вершин дерева при проходженні його у прямому порядку; послідовність листків дерева при проходженні його у зворотньому порядку; послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку. Виконати індивідуальне завдання згідно з варіантом. Варіанти завдань: Cтворити дзеркальне до заданого дерево. Вилучити з дерева всi листки. Вилучити з дерева всi вузли, що мають тільки одного безпосереднього нащадка. Вилучити з дерева всi вузли, що мають двох синів. Додати до дерева листки так, щоб воно стало строго бінарним деревом. Побудувати два бінарних дерева пошуку та визначити, чи є вони дзеркальним відображенням одне одного. Побудувати два бінарних дерева пошуку та визначити, чи можна одне дерево одержати з іншого шляхом вилучення однієї з його вершин. Знайти середнє геометричне значення всіх в...